
/*
 * Question: The maoshengdu of a binary tree is
 * defined as the maximum number of nodes on every
 * level times the height of the binary tree. Try
 * to calculate the maoshengdu of a binary tree.
 */

#include <iostream>
#include <queue>
#include "bitree.h"
using namespace std;

class bitree : public _bitree<bitree, char>
{
};

struct qnode{
    bitree *rt;
    int h;
};

int maoshengdu(bitree *rt)
{
    int h, m, c;
    qnode n, t;
    queue<qnode> q;

    h = 1; c = 0; m = 0;
    if(rt){
        n.rt = rt; n.h = 1;
        q.push(n);
    }
    while( !q.empty() ){
        n = q.front(); q.pop();
        if( n.h == h ) c++;
        else{
            m = c > m ? c : m;
            c = 1;
            h++;
        }
        if(n.rt->lchild){
            t.rt = n.rt->lchild;
            t.h = n.h + 1;
            q.push(t);
        }
        if( n.rt->rchild ){
            t.rt = n.rt->rchild;
            t.h = n.h + 1;
            q.push(t);
        }
    }

    return m * h;
}

int main()
{
    bitree *rt;

    bitree_create<bitree,char>(rt, "ex52.txt");
    cout << maoshengdu(rt) << endl;
    bitree_destory(rt);

    return 0;
}

